package com.haidechizi.backup.sort1;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 3, 5, 0, 1, 4, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序
     * 1.选取数组的第一个数为基准数，从高位开始，对于当高位的数小于基准数时，便和地位的数进行交换
     * 2.当低位的数大于基准数时，便和高位的数进行交换，一直到比较结束
     * 3.将基数赋值给低位的数
     * 4.对左右两侧的数进行递归排序
     *
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr, int start, int end) {
        // 递归结束条件
        if (start >= end) {
            return;
        }

        int position = arr[start];

        int low = start;
        int high = end;


        while (low < high) {
            // 高位的数大于基数，移动高位的位置
            while (low < high && arr[high] >= position) {
                high--;
            }
            // 将高位的值赋值给低位
            arr[low] = arr[high];
            while (low < high && arr[low] < position) {
                low++;
            }
            // 将低位的值赋值给高位
            arr[high] = arr[low];
        }
        // 将position赋值给低位
        arr[low] = position;
        // 对低位左侧的数据进行递归排序
        quickSort(arr, start, low);
        // 对低位右侧的数据进行递归排序
        quickSort(arr, low + 1, end);
    }
}
